package ClassicalSortingAlgorithm;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: ClassicalSortingAlgorithm
 * @Author: song
 * @CreateTime: 2022-09-17  21:49
 * @Description: 稳定性：稳定
 * 时间复杂度 ：最佳：O(n) ，最差：O(n2)， 平均：O(n2)
 * 空间复杂度 ：O(1)
 * 排序方式 ：In-place
 * @Version: 1.0
 */

public class insertSort {
    public static void main(String[] args) {
        int[] nums = {3,7,5,2,11,89,34,14,25,61};
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
        insertSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }
    public static int[] insertSort(int[] nums){
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j-1]){
                    int temp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = temp;
                }
            }
        }

        return nums;
    }
}
